package leetcode_61_80;

public class removeDuplicates_80 {
    /**
     * 一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
     *
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        /**
         * 想法是记录删除元素的个数，然后向后寻找元素
         *
         * 写的巨生气，感觉自己写法太蠢比了
         */
        int  count=1, //数字的个数
                removed=0; //已经被删除的数字个数
        for (int i=0;i<nums.length-removed;){
            boolean flag=true;           //是否需要往后进位
            if (count - 2 > 0) {
                removed += count - 2;
                if (i >= nums.length - removed) break; //每次更新完removed，进行判断
                int t=count-2;
                for (int j=0;i+ j + removed<nums.length&&j<t;j++)  //将需要赋值的全部处理完
                    nums[i+j] = nums[i+ j + removed];
                i+=t;  //这里进完位，下边就不需要进位了
                flag=false;
            } else //上个数字没有超过数量，直接赋值
                nums[i] = nums[i + removed];
            //计算数字的数量
            count=1;//重置数字
            for (int t = i + removed; t < nums.length-1 && nums[t] == nums[t + 1]; t++) //计算后边多少位重复的数字
                count++;
            if (flag) { //没有进过位时
                if (count > 2)
                    i += 2;  //可以保存两个
                else  //不超过2，按部就班赋值
                    i++;
            }
        }
        return nums.length-removed;
    }

    /**
     * 官解的简洁写法
     * 让解法更具有一般性，将原问题的「保留 2 位」修改为「保留 k 位」。
     * @param nums
     * @return
     */
    public int removeDuplicates2(int[] nums) {
        int k=2;
        int u = 0;
        for (int x : nums) {
            if (u < k || nums[u - k] != x)  //当数字数量小于k，或者开始进行下一个数字时，赋值
                nums[u++] = x;
        }
        return u;
    }
}
